#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>>dp(n + 2);
        for (int i = 0; i < dp.size(); ++i)
            dp[i].resize(n + 2);
        for (int i = n; i > 0; --i) {
            for (int j = i+1; j <= n; ++j) {
                int min_ = INT32_MAX;
                for (int k = i; k <= j; ++k) {
                    int tmp = k + max(dp[i][k - 1], dp[k + 1][j]);
                    min_ = min(min_, tmp);
                }
                dp[i][j] = min_;
            }
        }
        return dp[1][n];
    }
};